#include "headfiles.h"

using namespace std;

static bool leftRotation(NODE * &root) {
    NODE *temp = root->right;
    temp->p = root->p;
    if (temp->p) {
        if (temp->p->left == root) {
            temp->p->left = temp;
        }
        else {
            temp->p->right = temp;
        }
    }

    root->right = temp->left;
    if (root->right) {
        root->right->p = root;
    }

    temp->left = root;
    root->p = temp;

    root = temp;

    return true;
}

static bool rightRotation(NODE * &root) {
    NODE *temp = root->left;
    temp->p = root->p;
    if (temp->p) {
        if (temp->p->left == root) {
            temp->p->left = temp;
        }
        else {
            temp->p->right = temp;
        }
    }


    root->left = temp->right;
    if (root->left) {
        root->left->p = root;
    }

    temp->right = root;
    root->p = temp;

    root = temp;

    return true;
}

static int binaryTreeHeight(NODE *root) {
    if (root == NULL) {
        return 0;
    }

    int left_height, right_height;
    left_height = 1;
    right_height = 1;
    if (root->left) {
        left_height = 1 + binaryTreeHeight(root->left);
    }

    if (root->right) {
        right_height = 1 + binaryTreeHeight(root->right);
    }

    return (left_height > right_height) ? left_height : right_height;
}

static int balanceFactor(NODE *root) {
    if (root == NULL) {
        return 0;
    }

    int left_height, right_height;
    left_height = binaryTreeHeight(root->left);
    right_height = binaryTreeHeight(root->right);

    return left_height - right_height;
}

bool nodeRebalance(NODE *&n) {
    if (n == NULL) {
        return true;
    }

    int balance_factor;
    balance_factor = balanceFactor(n);
    if (balance_factor == 2) {
        NODE *l = n->left;
        if (balanceFactor(l) == -1) {
            leftRotation(l);
        }

        rightRotation(n);
    }
    else if (balance_factor == -2) {
        NODE *r = n->right;
        if (balanceFactor(r) == 1) {
            rightRotation(r);
        }

        leftRotation(n);
    }

    return true;
}

NODE * treeRebalance(NODE *&n) {
    if (n == NULL) {
        return NULL;
    }

    bool ret;
    ret = nodeRebalance(n);

    NODE *p = n->p;
    NODE *root = n;
    while (p) {
        ret = nodeRebalance(p);
        root = p;
        p = p->p;
    }

    return root;
}

bool addNode(NODE *root, NODE *node) {
	NODE *child = root;
	while (child) {
		if (child->i > node->i) {
			if (child->left) {
				child = child->left;
			}
			else {
				child->left = node;
				node->p = child;
                break;
			}
		}
		else if (child->i < node->i) {
			if (child->right) {
				child = child->right;
			}
			else {
				child->right = node;
				node->p = child;
                break;
			}
		}
		else {
			return true;
		}
	}

    return true;
}

bool addNodeRecur(NODE *root, NODE *node) {
	if (root->i == node->i) {
		return true;
	}
	else if (root->i > node->i) {
		if (root->left) {
			return addNodeRecur(root->left, node);
		}
		else {
			root->left = node;
			node->p = root;
		}
	}
	else {
		if (root->right) {
			return addNodeRecur(root->right, node);
		}
		else {
			root->right = node;
			node->p = root;
		}
	}

	return true;
}

NODE *createBinSearchTree(char *file_name,
						  NODE** &node_list,
						  int &node_num) {
	if (file_name == NULL) {
		cout << "File name is NULL!" << endl;
		return NULL;
	}

	fstream nf;
	nf.open(file_name, fstream::in);
	if (!nf.is_open()) {
		cout << "File " << file_name << " open error!\n" << endl;
		return NULL;
	}

	// Allocate buffer to store node pointers
	node_list = (NODE **) malloc(sizeof(NODE *) * 1000);
	if (node_list == NULL) {
		cout << "Allocate buffer for node list error!" << endl;
		return NULL;
	}
	node_num = 0;

	string ss;
	NODE *root = NULL;
	while (nf >> ss) {
		if (ss.empty()) {
			return root;
		}

		int val = atoi(ss.c_str());
        cout << "val = " << val << endl;
		NODE *n = (NODE *)malloc(sizeof(NODE));
		node_list[node_num++] = n;
		memset(n, 0, sizeof(NODE));
		n->i = val;

		if (root == NULL) {
			root = n;
            continue;
		}
		
		if (!addNode(root, n)) {
			cout << "Add node error!" << endl;
			return root;
		}

        root = treeRebalance(n->p);
	}

	return root;
}


